package com.zjj.algorithm.learning.atguigu.linkedlist;

/**
 * 双向链表测试
 * @author zjj_admin
 * @date 2022/11/2 22:26
 */
public class DoubleLinkedListDemo {

    public static void main(String[] args) {
        DoubleLinkedList linkedList = new DoubleLinkedList();
        //先创建节点
        HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨");
        HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟");
        HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星");
        HeroNode2 hero4 = new HeroNode2(4, "林冲", "豹子头");



        linkedList.addHero(hero3);
//        linkedList.addHero(hero1);
//        linkedList.addHero(hero3);

//        linkedList.addHero(hero3);
        linkedList.addHero(hero2);
//        linkedList.addHero(hero4);
//        linkedList.addHero(hero2);

        linkedList.show();
    }
}



class DoubleLinkedList{
    /**
     * 头结点，不存储数据
     */
    public HeroNode2 head = new HeroNode2(0,"","");

    /**
     * 添加一个英雄
     * 当我们不考虑排序时
     * 1、找到最后一个节点
     * 2、将最后一个节点的 next 指向新添加的节点
     * @param heroNode
     */
    public void addHero(HeroNode2 heroNode){
        //因为head节点不动，所以需要一个临时的节点，用于找到最后一个节点
        HeroNode2 temp = head;
        //找到最后一个节点
        while (true){
            if(temp.next == null){
                break;
            }
            //当没有遍历到最后一个节点时，将temp后移，直到最后一个节点
            temp = temp.next;
        }
        //将while结束时，temp就是最后一个节点，将temp的next给新添加的节点即可
        temp.next = heroNode;
        heroNode.pre = temp;
    }


    /**
     * 添加节点，根据 No 的排序进行添加
     */
    public void addHeroByOrder(HeroNode2 heroNode){
        //依旧头节点不动，所以还是需要一个临时指针
        //单链表，temp位于添加位置的前一个节点
        HeroNode2 temp = head;

        //标识添加的英雄标号编号是否存在
        boolean flag = false;
        //首先需要找到新添加的节点应该添加在什么位置
        while (true){
            //此时添加的位置在最后一个节点
            if(temp.next == null){
                break;
            }
            //找到了需要添加的位置
            if(temp.next.no > heroNode.no){
                break;
            }
            //判断需要添加的位置是否和新加入的节点的编号是否相同
            // 这里必须是 temp.next.no 不能是 temp.no，否则可能死循环
            if(temp.next.no == heroNode.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }

        if (flag) {
            System.out.println("存在需要相同的英雄，不能添加：" + heroNode.no);
            return;
        }
        //添加数据
        temp.next = heroNode;
        heroNode.pre = temp;
    }


    /**
     * 修改节点信息，根据编号修改
     * @param newHeroNode
     */
    public void updateHero(HeroNode2 newHeroNode){
        if (this.head.next == null) {
            System.out.println("链表为空，不能修改");
            return;
        }
        HeroNode2 temp = head.next;
        //标注在链表中是否存在这个节点
        boolean flag = false;
        while (true){
            //当遍历结束都没找到
            if(temp == null){
                break;
            }
            //当找到了时
            if(temp.no == newHeroNode.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (!flag) {
            System.out.println("不存在当前节点，不能修改");
            return;
        }
        temp.name = newHeroNode.name;
        temp.nickname = newHeroNode.nickname;
    }


    /**
     * 删除节点
     * 定义一个临时变量 temp，为需要删除节点的前一个节点
     * 删除核心代码为 temp.next = temp.next.next;
     * @param HeroNode2 需要删除的节点
     */
    public void deleteHero(HeroNode2 HeroNode2){
        HeroNode2 temp = head;
        //标记是否存在需要删除的数据
        boolean flag = false;
        while (true){
            if(temp == null){
                break;
            }
            if(temp.next.no == HeroNode2.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (!flag) {
            System.out.println("不存在当前节点，删除失败");
            return;
        }
        //删除节点
        temp.pre.next = temp.next;
        temp.next.pre = temp.pre;
    }

    /**
     * 返回链表的有效长度，不算头结点
     * @param head
     * @return
     */
    public static int getLength(HeroNode2 head){
        if(head.next == null){
            return 0;
        }
        int length = 0;
        HeroNode2 curr = head.next;
        while (curr != null){
            length ++;
            curr = curr.next;
        }
        return length;
    }





    /**
     * 显示单链表中的数据，将链表中的数据全部打印
     *
     */
    public void show(){
        if (this.head.next == null){
            System.out.println("单链表中不存在节点");
            return;
        }
        //定义一个临时变量，用于存储头结点的下一个节点
        HeroNode2 temp = this.head.next;
        //依次遍历，将节点信息打印
        while (true){
            if(temp == null){
                break;
            }
            //打印
            System.out.println(temp);
            //将节点指向下一个节点
            temp = temp.next;
        }
    }

}


class HeroNode2{

    /**
     * 此处定义为 public 是为了方便测试，真实环境不建议这样
     */
    public int no;
    public String name;
    public String nickname;
    /**
     * 下一个节点，当为 null时就表示为最后一个节点
     */
    public HeroNode2 next;
    public HeroNode2 pre;


    public HeroNode2(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }


    @Override
    public String toString() {
        return "HeroNode2{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}
